package ljl.alg.jianzhioffer.round3.medium;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _56_singleNumber2 {

    /**
     * 这不是脑子正常的人能想出来的
     * 而且我先在也不是很懂
     * */
    class bu_hao_li_jie {
        /*
         * 0 0 -> 0 1 -> 1 0 -> 0 0
         * 0 1    1 0    0 0    0 1
         * 1 0    0 0    0 1    1 0
         *
         * 他们是这么说的：先算的 b 所以 a 要在 b 的基础上算
         * why？
         * */
        public int singleNumber(int[] nums) {
            int a = 0, b = 0;
            for (int num : nums) {
                b = ~a & (b ^ num);
                a = ~b & (a ^ num);
            }
            return b;
        }
    }

    /**
     * 这个方法得小心溢出，有好几处可能溢出，我干
     * */
    class math {
        public int singleNumber(int[] nums) {
            long sum = 0;
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                sum += num;
                set.add(num);
            }
            long distinctSum = 0;
            for (Integer each : set)
                distinctSum += each;
            return (int)((distinctSum * 3 - sum) / 2);
        }
    }

    /**
     * 这个怎么最慢？
     * */
    class normal_youth {
        public int singleNumber(int[] nums) {
            int[] bits = new int[32];
            for (int num : nums) {
                int bit = 1;
                for (int i = 0; i < 32; i++) {
                    if ((num & bit) != 0)
                        bits[i]++;
                    bit <<= 1;
                }
            }
            int res = 0;
            for (int i = 31; i >= 0; i--) {
                res <<= 1;
                res |= bits[i] % 3 == 0 ? 0 : 1;
            }
            return res;
        }
    }

    /**
     * 他们说 map 好
     * 也很慢妈的
     * */
    class map {
        public int singleNumber(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0));
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() == 1)
                    return entry.getKey();
            }
            return 0;
        }
    }
}
